Electronic design automation (EDA) toolsets are utilized by circuit developers to design and fully test their circuit designs before manufacturing (i.e., fabricating or otherwise producing) physical circuit structures. The term “circuit design” refers to a software-based description of an integrated circuit (IC) at any stage of the development process, from an initial circuit concept (general system level description) to a final taped-out description suitable for transfer to a fabrication facility. Modern EDA toolsets typically include a suite of tools that seamlessly integrate different operations associated with the design/development of a circuit design, such as system and logic design tools, synthesis and layout tools, routing and mask preparation tools, and tools for various types of testing and verification. Because modern ICs (e.g., System-on-Chip devices) can include billions of transistors and other circuit elements arranged in thousands interconnected circuits (e.g., processors, memory arrays, etc.), EDA toolsets have become essential in development of all modern circuit designs. Moreover, because the post-fabrication discovery of design flaws can cause significant production delays and significantly affect profitability of a circuit device, EDA tools have become essential in the pre-fabrication testing/verification of modern circuit designs. That is, without EDA software tools, the commercially viable development a modern circuit design from concept to physical circuit device would be practically impossible.
Layout verification (aka physical verification) is a specific testing/verification process that verifies the manufacturability of a circuit design. Design Rule Checking (DRC) is one type of layout verification that involves verifying that a circuit design's layout conforms with established design rules, which are geometric constraints imposed on circuit device layout to ensure that the circuit design functions properly and can be produced with an acceptable yield. Other layout verification processes include layout versus schematic (LVS), XOR check, antenna check and electrical rule check (ERC).
When applied to modern ICs, DRC operations involving even simple design rules can be extremely expensive computationally. A conventional DRC operation generally involves utilizing a powerful two-dimensional geometry engine that supports geometric operations such as Boolean operations like AND, OR, NOT, XOR; sizing operations like grow/shrink horizontal/vertical/diagonal, along with other operations like merge, shift, flip, cut and smooth, as well as all-angle geometry for true Euclidean distance calculations. Individual rules are typically checked individually over an entire layout region, as well as individual rule values of same rule (e.g., a check against the minimum value for a rule, and another check against a preferred value for the same rule). Each check basically runs an independent sequence of geometric operations, and numerous passes through the layout region are required, with each geometric operation involving receives layer data and/or additional data as input data, performing the designated geometric, sizing or other operation, and then producing new layers and/or additional data as output data. When applied to the layout of a billion-plus-transistor circuit design associated with a modern IC, it is readily apparent that substantial processing power and vast memory resources are required to perform DRC on modern circuit designs.
Conventional layout verification tools, such as the IC Validator tool produced by Synopsys, Inc. of Mountain View, Calif., USA, deal with the massive amount of processing and data associated with a DRC (or other layout verification) operation by implementing parallel computing and memory management schemes to facilitate completion of DRC operations in an acceptable timeframe. Parallel computing of a DRC operation typically involves dividing the total number of rule checks to be processed in to sets of geometric operations, and then assigning each geometric operation set to a specific CPU of a parallel computing system (e.g., a multi-core or multi-processor computer, a computer cluster, a massively parallel processor array, or a computing grid). While a given CPU is executing its assigned set of geometric operations, a memory management scheme is utilized to coordinate the efficient allocation of shared main memory resources (e.g., high-speed random-access memory) among various interconnected CPUs, for example, of a multi-core or multi-processor computer. By executing the multiple rule check sets in parallel (i.e., such that multiple CPUs process different rule check sets simultaneously) using efficient memory management schemes, parallel computing substantially reduces the amount of time required to complete DRC processing of a modern IC's circuit design (i.e., in comparison to a single CPU approach).
FIG. 7 depicts a generalized and greatly simplified series of operations executed by a geometry engine 60 and a memory manager 70 of a conventional layout verification tool 50 at the beginning of a current (next-scheduled) geometric operation of a geometric operation set assigned to a given CPU.
Referring to the top of FIG. 7, geometry engine 60 estimates the amount of main memory that will be needed (block 61) before beginning the current geometric operation. The estimated memory amount is typically accurately generated using established proprietary techniques. Alternatively, a rough estimate may be calculated by multiplying a fixed amount of memory with the number of geometric shapes to be processed during the current geometric operation. Geometry engine 60 then sends a request 63 for the estimated memory amount to memory manager 70 (block 62).
Next, memory manager 70 determines whether sufficient main memory is available to process the current geometric operation. As indicated by dot-line-arrow 81, a current amount of available memory 85 in main memory 80 is provided to memory manager 70 using known techniques. Upon receiving request 63, memory manager 70 compares the estimated memory amount with currently available memory 85 (block 72). Referring to decision block 73, if the amount of available memory 85 is equal to or greater than the estimated memory amount requested (Yes branch from decision block 73), then memory manager 70 transmits memory address information or otherwise operably instructs geometry engine 60 to proceed with the current geometric operation (block 74). Conversely, if the amount of available memory 85 is less than the estimated memory amount requested (No branch from decision block 73), then memory manager 70 operably instructs geometry engine 60 to postpone (delay) execution of the current geometric operation.
Upon receiving an instruction from memory manager 70, geometry engine 60 then either performs the current geometric operation (block 65) or postpones the current geometric operation for an established time period (block 66). Referring to block 65, performance of the current geometric operation by geometry engine 60 generally involves reading previously generated (old) layer and/or additional data 95-1 read from disk memory 90 as input (indicated by arrow 91-1), writing and reading temporary data (TEMP DATA) in available main memory 85 (indicated by dashed-line arrows 83), and then, upon completion of the current geometric operation, writing as output updated (new) layer and/or additional data 90-2 to disk memory 90. Conversely, when memory manager 70 instructs geometry engine 60 to postpone (delay) execution of the current geometric operation (block 66), geometry engine 60 waits a predetermined delay period and then re-submits the request for memory (i.e., as indicated by arrow 67).
As indicated in FIG. 7, conventional layout verification processes are characterized by utilizing main memory 80 to store temporary data files during execution of a geometric operation, and disk memory 90 to store old layer data files 90-1 generated by previously performed geometric operations for use as input in subsequently performed geometric operations. The motivation for using this arrangement in conventional layout verification tools is to maximize the amount of available main memory for performing current geometric operations, thereby attempting to minimize processing time by way of minimizing the chance of delays caused by insufficient available memory. However, as the size of circuit designs for modern ICs continues to increase, it is becoming increasingly expensive to set-up and reliably maintain the large-scale remote disk servers needed to store all layer data files generated during a DRC process.
Another increasingly significant problem associated with conventional layout verification tools is processing delays caused by increasingly longer disk access times. It is generally understood that it takes less time for a given CPU to access data stored in main memory than to access data stored on a local disk (i.e., main memory access times are faster than disk access times). However, while traditional CPU-local-disk access times may have been tolerable in early layout verification tools, there is an increasing trend toward implementing conventional distributed layout verification tools using large compute clusters and distributed file systems in order to facilitate storage of the massive amounts of layer data generated during layout verification of modern ICs. When conventional distributed layout verification tools are implemented in such networked systems, the layer data is transmitted through the network bus between distributed CPUs and disk storage, which adds more delay on top of a traditional CPU-local-disk access time. When applied to modern IC circuit designs, the disk access times associated with implementing conventional distributed layout verification tools in networked systems can add significant delay to completion of layout verification processes.
What is needed is a method for managing memory resources during a DRC (or other layout verification) process that balances memory usage between geometric operations and file storage in a way that both maximizes geometric operation processing speed and minimizes the use of disk storage.